package com.lw.leetcode.sort.b;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 1727. 重新排列后的最大子矩阵
 *
 * @author liw
 * @version 1.0
 * @date 2022/2/10 13:41
 */
public class LargestSubmatrix {

    public int largestSubmatrix(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        int res = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == 1) {
                    matrix[i][j] += matrix[i - 1][j];
                }
            }
        }
        for (int[] arr : matrix) {
            Arrays.sort(arr);
            for (int j = m - 1; j >= 0; j--) {
                int height = arr[j];
                if (height == 0) {
                    break;
                }
                res = Math.max(res, height * (m - j));
            }
        }
        return res;
    }


}
